翻訳と辞書 Words near each other ・ Schonfeld ・ Schongau ・ Schongau, Bavaria ・ Schongau, Lucerne ・ Schoning ・ Schonland ・ Schonsee, Edmonton ・ Schonstedt Instrument Company ・ Schonstett ・ Schonungen ・ Schonwald ・ Schoodic Peninsula ・ Schoof ・ Schoof's algorithm ・ Schoofs Nunatak ・ Schoof–Elkies–Atkin algorithm ・ School ・ School (disambiguation) ・ School (TV series) ・ School 13 ・ School 2013 ・ School 518 ・ School 87 ・ School Addition Historic District ・ School Administrative Unit 31 ・ School and College Ability Test ・ School and university in literature ・ School Around the Corner ・ School assembly ・ School Astronomical Olympiad by Correspondence Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Schoof–Elkies–Atkin algorithm ： ウィキペディア英語版 Schoof–Elkies–Atkin algorithm The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. Its primary application is in elliptic curve cryptography. The algorithm is an extension of Schoof's algorithm by Noam Elkies and A. O. L. Atkin to significantly improve its efficiency (under heuristic assumptions). ==Details== The Elkies-Atkin extension to Schoof's algorithm works by restricting the set of primes $S\; =\; \backslash$ considered to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime $l$ is called an Elkies prime if the characteristic equation: $\backslash phi^2-t\backslash phi+\; q\; =\; 0$ splits over $\backslash mathbb\_l$, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the Schoof–Elkies–Atkin algorithm. The first problem to address is to determine whether a given prime is Elkies or Atkin. In order to do so, we make use of modular polynomials $\backslash Phi\_l(X,Y)$ that parametrize pairs of $l$-isogenous elliptic curves in terms of their j-invariants (in practice alternative modular polynomials may also be used but for the same purpose). If the instantiated polynomial $\backslash Phi\_l(X,j(E))$ has a root $j(E\text{'})$ in $\backslash mathbb\_q$ then $l$ is an Elkies prime, and we may compute a polynomial $f\_l(X)$ whose roots correspond to points in the kernel of the $l$-isogeny from $E$ to $E\text{'}$. The polynomial $f\_l$ is a divisor of the corresponding division polynomial used in Schoof's algorithm, and it has significantly lower degree, $O(l)$ versus $O(l^2)$. For Elkies primes, this allows one to compute the number of points on $E$ modulo $l$ more efficiently than in Schoof's algorithm. In the case of an Atkin prime, we can gain some information from the factorization pattern of $\backslash Phi\_l(X,j(E))$ in $\backslash mathbb\_l()$, which constrains the possibilities for the number of points modulo $l$, but the asymptotic complexity of the algorithm depends entirely on the Elkies primes. Provided there are sufficiently many small Elkies primes (on average, we expect half the primes $l$ to be Elkies primes), this results in a reduction in the running time. The resulting algorithm is probabilistic (of Las Vegas type), and its expected running time is, heuristically, $\backslash tilde(\backslash log^4\; q)$, making it more efficient in practice than Schoof's algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Schoof–Elkies–Atkin algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.